// Magic Software, Inc.
// http://www.magic-software.com
// Copyright (c) 2000, All Rights Reserved
//
// Source code from Magic Software is supplied under the terms of a license
// agreement and may not be copied or disclosed except in accordance with the
// terms of that agreement.  The various license agreements may be found at
// the Magic Software web site.  This file is subject to the license
//
// FREE SOURCE CODE
// http://www.magic-software.com/License/free.pdf

#include "MgcRTLib.h"
#include "MgcVetTable.h"

//----------------------------------------------------------------------------
// table methods
//----------------------------------------------------------------------------
MgcVetTable::MgcVetTable ()
{
}
//----------------------------------------------------------------------------
MgcVetTable::~MgcVetTable ()
{
    bool bFound;
    Vertex* pkVertex;
    Edge* pkEdge;
    Triangle* pkTriangle;

    bFound = m_kVList.GetFirst(pkVertex);
    while ( bFound )
    {
        delete pkVertex;
        bFound = m_kVList.GetNext(pkVertex);
    }

    bFound = m_kEList.GetFirst(pkEdge);
    while ( bFound )
    {
        delete pkEdge;
        bFound = m_kEList.GetNext(pkEdge);
    }

    bFound = m_kTList.GetFirst(pkTriangle);
    while ( bFound )
    {
        delete pkTriangle;
        bFound = m_kTList.GetNext(pkTriangle);
    }
}
//----------------------------------------------------------------------------
MgcVetTable::Vertex* MgcVetTable::GetVertex (unsigned int uiV)
{
    Vertex* pkVertex;
    bool bFound = m_kVList.GetFirst(pkVertex);
    while ( bFound )
    {
        if ( pkVertex->m_uiV == uiV )
            return pkVertex;

        bFound = m_kVList.GetNext(pkVertex);
    }
    return 0;
}
//----------------------------------------------------------------------------
MgcVetTable::Edge* MgcVetTable::GetEdge (unsigned int uiV0, unsigned int uiV1)
{
    Edge* pkEdge;
    bool bFound = m_kEList.GetFirst(pkEdge);
    while ( bFound )
    {
        if ( (pkEdge->m_auiV[0] == uiV0 && pkEdge->m_auiV[1] == uiV1)
        ||   (pkEdge->m_auiV[0] == uiV1 && pkEdge->m_auiV[1] == uiV0) )
        {
            return pkEdge;
        }

        bFound = m_kEList.GetNext(pkEdge);
    }
    return 0;
}
//----------------------------------------------------------------------------
MgcVetTable::Triangle* MgcVetTable::GetTriangle (unsigned int uiV0,
    unsigned int uiV1, unsigned int uiV2)
{
    Triangle* pkT;
    bool bFound = m_kTList.GetFirst(pkT);
    while ( bFound )
    {
        // All even permuations are checked.  Odd permutations are considered
        // new triangles to support double-sided triangles.
        if ( (pkT->m_auiV[0] == uiV0 &&
              pkT->m_auiV[1] == uiV1 &&
              pkT->m_auiV[2] == uiV2)
        ||   (pkT->m_auiV[0] == uiV1 &&
              pkT->m_auiV[1] == uiV2 &&
              pkT->m_auiV[2] == uiV0)
        ||   (pkT->m_auiV[0] == uiV2 &&
              pkT->m_auiV[1] == uiV0 &&
              pkT->m_auiV[2] == uiV1) )
        {
            return pkT;
        }

        bFound = m_kTList.GetNext(pkT);
    }
    return 0;
}
//----------------------------------------------------------------------------
MgcVetTable::Triangle* MgcVetTable::AddTriangle (unsigned int uiT,
    unsigned int uiV0, unsigned int uiV1, unsigned int uiV2)
{
    if ( uiV0 == uiV1 || uiV1 == uiV2 || uiV2 == uiV0 )
    {
        // degenerate triangles not allowed
        return 0;
    }

    Triangle* pkT = GetTriangle(uiV0,uiV2,uiV2);
    if ( pkT )
    {
        // triangle already in table
        return pkT;
    }

    // create vertices
    Vertex* pkV0 = GetVertex(uiV0);
    if ( !pkV0 )
    {
        pkV0 = new Vertex(uiV0);
        m_kVList.Add(pkV0);
    }

    Vertex* pkV1 = GetVertex(uiV1);
    if ( !pkV1 )
    {
        pkV1 = new Vertex(uiV1);
        m_kVList.Add(pkV1);
    }

    Vertex* pkV2 = GetVertex(uiV2);
    if ( !pkV2 )
    {
        pkV2 = new Vertex(uiV2);
        m_kVList.Add(pkV2);
    }

    // create edges
    Edge* pkE0 = GetEdge(uiV0,uiV1);
    if ( !pkE0 )
    {
        pkE0 = new Edge(uiV0,uiV1,pkV0,pkV1);
        m_kEList.Add(pkE0);
    }

    Edge* pkE1 = GetEdge(uiV1,uiV2);
    if ( !pkE1 )
    {
        pkE1 = new Edge(uiV1,uiV2,pkV1,pkV2);
        m_kEList.Add(pkE1);
    }

    Edge* pkE2 = GetEdge(uiV2,uiV0);
    if ( !pkE2 )
    {
        pkE2 = new Edge(uiV2,uiV0,pkV2,pkV0);
        m_kEList.Add(pkE2);
    }

    // create triangle
    pkT = new Triangle(uiT,uiV0,uiV1,uiV2,pkV0,pkV1,pkV2,pkE0,pkE1,pkE2);
    m_kTList.Add(pkT);

    // update vertex lists
    pkV0->AddEdge(pkE0);
    pkV0->AddEdge(pkE2);
    pkV0->AddTriangle(pkT);
    pkV1->AddEdge(pkE0);
    pkV1->AddEdge(pkE1);
    pkV1->AddTriangle(pkT);
    pkV2->AddEdge(pkE1);
    pkV2->AddEdge(pkE2);
    pkV2->AddTriangle(pkT);

    // update edge lists
    pkE0->AddTriangle(pkT);
    pkE1->AddTriangle(pkT);
    pkE2->AddTriangle(pkT);

    return pkT;
}
//----------------------------------------------------------------------------
unsigned int MgcVetTable::RemoveTriangle (unsigned int uiV0,
    unsigned int uiV1, unsigned int uiV2)
{
    m_kVDeleteList.RemoveAll();
    m_kTDeleteList.RemoveAll();
    m_kTModifiedList.RemoveAll();

    Triangle* pkTriangle = GetTriangle(uiV0,uiV1,uiV2);
    if ( !pkTriangle )
    {
        // triangle not in table
        return (unsigned int)(~0);
    }

    unsigned int uiT = pkTriangle->m_uiT;
    m_kTDeleteList.Add(uiT);
    DeleteTriangle(pkTriangle);
    return uiT;
}
//----------------------------------------------------------------------------
void MgcVetTable::DeleteTriangle (Triangle* pkTriangle)
{
    int i;
    Vertex* pkVertex;
    Edge* pkEdge;

    // update vertex lists
    for (i = 0; i < 3; i++)
    {
        pkVertex = pkTriangle->m_apkV[i];
        pkVertex->m_kTList.Remove(pkTriangle);
        if ( pkVertex->m_kTList.GetQuantity() == 0 )
        {
            // The vertex is not shared by any other triangles.  Tell its
            // adjacent vertices that their edges to this vertex need to be
            // removed.
            pkEdge = pkTriangle->m_apkE[i];
            pkVertex->m_kEList.Remove(pkEdge);
            if ( pkEdge->m_apkV[0] == pkVertex )
                pkEdge->m_apkV[1]->m_kEList.Remove(pkEdge);
            else
                pkEdge->m_apkV[0]->m_kEList.Remove(pkEdge);

            pkEdge = pkTriangle->m_apkE[(i+2)%3];
            pkVertex->m_kEList.Remove(pkEdge);
            if ( pkEdge->m_apkV[0] == pkVertex )
                pkEdge->m_apkV[1]->m_kEList.Remove(pkEdge);
            else
                pkEdge->m_apkV[0]->m_kEList.Remove(pkEdge);
        }
    }

    // update edge lists
    for (i = 0; i < 3; i++)
    {
        pkEdge = pkTriangle->m_apkE[i];
        pkEdge->m_kTList.Remove(pkTriangle);
        if ( pkEdge->m_kTList.GetQuantity() == 0 )
        {
            // The edge is not shared by any other triangles.  Tell its
            // vertices that the edge needs to be removed.
            pkEdge->m_apkV[0]->m_kEList.Remove(pkEdge);
            pkEdge->m_apkV[1]->m_kEList.Remove(pkEdge);
        }
    }

    // remove vertices from table (if necessary)
    for (i = 0; i < 3; i++)
    {
        pkVertex = pkTriangle->m_apkV[i];
        if ( pkVertex->m_kTList.GetQuantity() == 0 )
        {
            m_kVList.Remove(pkVertex);
            m_kVDeleteList.Add(pkVertex->m_uiV);
            delete pkVertex;
        }
    }

    // remove edges from table (if necessary)
    for (i = 0; i < 3; i++)
    {
        pkEdge = pkTriangle->m_apkE[i];
        if ( pkEdge->m_kTList.GetQuantity() == 0 )
        {
            m_kEList.Remove(pkEdge);
            delete pkEdge;
        }
    }

    // remove triangle from table
    m_kTList.Remove(pkTriangle);
    delete pkTriangle;
}
//----------------------------------------------------------------------------
bool MgcVetTable::CollapseEdge (unsigned int uiVKeep, unsigned int uiVThrow)
{
    m_kVDeleteList.RemoveAll();
    m_kTDeleteList.RemoveAll();
    m_kTModifiedList.RemoveAll();

    // check for existence of edge
    Edge* pkCollapse = GetEdge(uiVKeep,uiVThrow);
    if ( !pkCollapse )
        return false;

    // get 'throw' vertex
    Vertex* pkVThrow = GetVertex(uiVThrow);

    // determine if 'throw' vertex is adjacent only to collapse triangles
    unsigned int uiQuantity0 = pkCollapse->m_kTList.GetQuantity();
    assert( uiQuantity0 > 0 );
    unsigned int uiQuantity1 = pkVThrow->m_kTList.GetQuantity();
    assert( uiQuantity1 >= uiQuantity0 );
    bool bModify = (uiQuantity0 != uiQuantity1);
    uiQuantity1 -= uiQuantity0;

    // Delete triangles sharing the collapse edge.  The unusual loop
    // structure is used because deleting the last triangle of the list has
    // the side effect of deleting pkCollapse from the table.  After the loop
    // ends, pkCollapse is a dangling pointer.
    Triangle* pkTriangle;
    pkCollapse->m_kTList.GetFirst(pkTriangle);
    while ( true )
    {
        m_kTDeleteList.Add(pkTriangle->m_uiT);
        DeleteTriangle(pkTriangle);
        if ( --uiQuantity0 == 0 )
            break;

        pkCollapse->m_kTList.GetNext(pkTriangle);
    }

    if ( bModify )
    {
        // Add new triangles and delete the old ones.  The unusual loop
        // structure is used because deleting the last triangle adjacent to
        // the 'throw' vertex has the side effect of deleting pkVThrow from
        // the table.  After the loop ends, pkVThrow is a dangling pointer.
        pkVThrow->m_kTList.GetFirst(pkTriangle);
        while ( true )
        {
            // compute vertices of new triangle
            unsigned int uiV[3];
            int i;
            for (i = 0; i < 3; i++)
            {
                if ( pkTriangle->m_auiV[i] == uiVThrow )
                    uiV[i] = uiVKeep;
                else
                    uiV[i] = pkTriangle->m_auiV[i];
            }

            // Vertices that were deleted when removing the collapsed edge
            // may be added back into the system by the next AddTriangle
            // call.  Make sure to remove the re-added ones from the delete
            // list.
            for (i = 0; i < 3; i++)
                m_kVDeleteList.Remove(uiV[i]);

            m_kTModifiedList.Add(pkTriangle->m_uiT);
            AddTriangle(pkTriangle->m_uiT,uiV[0],uiV[1],uiV[2]);
            DeleteTriangle(pkTriangle);
            if ( --uiQuantity1 == 0 )
                break;

            pkVThrow->m_kTList.GetNext(pkTriangle);
        }
    }

    return true;
}
//----------------------------------------------------------------------------
void MgcVetTable::Print (ostream& rkOstr)
{
    bool bVFound, bEFound, bTFound;
    Vertex* pkVertex;
    Edge* pkEdge;
    Triangle* pkTriangle;

    // vertices
    bVFound = m_kVList.GetFirst(pkVertex);
    while ( bVFound )
    {
        rkOstr << "vertex " << pkVertex->m_uiV << endl;
        rkOstr << "  " << pkVertex->m_kEList.GetQuantity() << " edges:";
        bEFound = pkVertex->m_kEList.GetFirst(pkEdge);
        while ( bEFound )
        {
            rkOstr << " <" << pkEdge->m_auiV[0] << "," << pkEdge->m_auiV[1]
                   << ">";
            bEFound = pkVertex->m_kEList.GetNext(pkEdge);
        }
        rkOstr << endl;

        rkOstr << "  " << pkVertex->m_kTList.GetQuantity() << " triangles:";
        bTFound = pkVertex->m_kTList.GetFirst(pkTriangle);
        while ( bTFound )
        {
            rkOstr << " <" << pkTriangle->m_auiV[0] << ","
                   << pkTriangle->m_auiV[1] << "," << pkTriangle->m_auiV[2]
                   << ">";
            bTFound = pkVertex->m_kTList.GetNext(pkTriangle);
        }
        rkOstr << endl;

        bVFound = m_kVList.GetNext(pkVertex);
    }

    // edges
    bEFound = m_kEList.GetFirst(pkEdge);
    while ( bEFound )
    {
        rkOstr << "edge <" << pkEdge->m_auiV[0] << "," << pkEdge->m_auiV[1]
               << ">" << endl;

        rkOstr << "  " << pkEdge->m_kTList.GetQuantity() << " triangles:";
        bTFound = pkEdge->m_kTList.GetFirst(pkTriangle);
        while ( bTFound )
        {
            rkOstr << " <" << pkTriangle->m_auiV[0] << ","
                   << pkTriangle->m_auiV[1] << "," << pkTriangle->m_auiV[2]
                   << ">";
            bTFound = pkEdge->m_kTList.GetNext(pkTriangle);
        }
        rkOstr << endl;

        bEFound = m_kEList.GetNext(pkEdge);
    }

    // triangles
    bTFound = m_kTList.GetFirst(pkTriangle);
    while ( bTFound )
    {
        rkOstr << "triangle <" << pkTriangle->m_auiV[0] << ","
               << pkTriangle->m_auiV[1] << "," << pkTriangle->m_auiV[2]
               << ">" << endl;

        bTFound = m_kTList.GetNext(pkTriangle);
    }
}
//----------------------------------------------------------------------------

//----------------------------------------------------------------------------
// vertex methods
//----------------------------------------------------------------------------
MgcVetTable::Vertex::Vertex (unsigned int uiV)
{
    m_uiV = uiV;
}
//----------------------------------------------------------------------------
MgcVetTable::Vertex::~Vertex ()
{
    m_kEList.RemoveAll();
    m_kTList.RemoveAll();
}
//----------------------------------------------------------------------------
void MgcVetTable::Vertex::AddEdge (Edge* pkEdge)
{
    Edge* pkSearch;
    bool bFound = m_kEList.GetFirst(pkSearch);
    while ( bFound )
    {
        if ( pkSearch == pkEdge )
            return;

        bFound = m_kEList.GetNext(pkSearch);
    }

    m_kEList.Add(pkEdge);
}
//----------------------------------------------------------------------------
void MgcVetTable::Vertex::AddTriangle (Triangle* pkTriangle)
{
    Triangle* pkSearch;
    bool bFound = m_kTList.GetFirst(pkSearch);
    while ( bFound )
    {
        if ( pkSearch == pkTriangle )
            return;

        bFound = m_kTList.GetNext(pkSearch);
    }

    m_kTList.Add(pkTriangle);
}
//----------------------------------------------------------------------------

//----------------------------------------------------------------------------
// edge methods
//----------------------------------------------------------------------------
MgcVetTable::Edge::Edge (unsigned int uiV0, unsigned int uiV1, Vertex* pkV0,
    Vertex* pkV1)
{
    m_auiV[0] = uiV0;
    m_auiV[1] = uiV1;
    m_apkV[0] = pkV0;
    m_apkV[1] = pkV1;
}
//----------------------------------------------------------------------------
MgcVetTable::Edge::~Edge ()
{
    m_kTList.RemoveAll();
}
//----------------------------------------------------------------------------
void MgcVetTable::Edge::AddTriangle (Triangle* pkTriangle)
{
    Triangle* pkSearch;
    bool bFound = m_kTList.GetFirst(pkSearch);
    while ( bFound )
    {
        if ( pkSearch == pkTriangle )
            return;

        bFound = m_kTList.GetNext(pkSearch);
    }

    m_kTList.Add(pkTriangle);
}
//----------------------------------------------------------------------------

//----------------------------------------------------------------------------
// triangle methods
//----------------------------------------------------------------------------
MgcVetTable::Triangle::Triangle (unsigned int uiT, unsigned int uiV0,
    unsigned int uiV1, unsigned int uiV2, Vertex* pkV0, Vertex* pkV1,
    Vertex* pkV2, Edge* pkE0, Edge* pkE1, Edge* pkE2)
{
    m_uiT = uiT;
    m_auiV[0] = uiV0;
    m_auiV[1] = uiV1;
    m_auiV[2] = uiV2;
    m_apkV[0] = pkV0;
    m_apkV[1] = pkV1;
    m_apkV[2] = pkV2;
    m_apkE[0] = pkE0;
    m_apkE[1] = pkE1;
    m_apkE[2] = pkE2;
}
//----------------------------------------------------------------------------
